5.9 KB · ⇊ 3 parts · ⤓ Micron 5.9 KB · ⤓ HTML 36.5 KB

top

Ein k {\displaystyle k} -partiter Graph ist in der Graphentheorie ein einfacher Graph, dessen Knotenmenge in k disjunkte Teilmengen zerfällt, sodass die Knoten jeder dieser Teilmengen untereinander nicht benachbart sind. Für k = 2 {\displaystyle k=2} heißen diese Graphen bipartite Graphen.

• Definitionen

• Beispiel Turán-Graph

• Eigenschaften

• Literatur

• Weblinks

• Einzelnachweise

Eine k-Partition eines Graphen G = ( V , E ) {\displaystyle G=(V,E)} ist eine Zerlegung der Knotenmenge V {\displaystyle V} in k {\displaystyle k} disjunkte Teilmengen V 1 , … … , V k {\displaystyle V_{1},\ldots ,V_{k}} , sodass keine adjazenten Knoten in der gleichen Menge V i {\displaystyle V_{i}} liegen, das heißt

∀ ∀ i ∈ ∈ { 1 , … … , k } : v ∈ ∈ V i ∧ ∧ w ∈ ∈ V i → → { v , w } ∉ E {\displaystyle \forall i\in \{1,\ldots ,k\}:v\in V_{i}\wedge w\in V_{i}\rightarrow \{v,w\}\not \in E} .

Man beachte, dass eine solche k-Partition nicht eindeutig ist. Es ist durchaus möglich, dass es mehrere k-Partitionen gibt, die diese Eigenschaft erfüllen. Ein Graph heißt nun k-partit, falls er eine k-Partition besitzt. Man nennt den Graphen vollständig k-partit, falls außerdem jeder Knoten mit allen Knoten aller anderen k-Partitionen verbunden ist, wenn also gilt:

∀ ∀ i ≠ ≠ j ∈ ∈ { 1 , … … , k } : v ∈ ∈ V i ∧ ∧ w ∈ ∈ V j → → { v , w } ∈ ∈ E {\displaystyle \forall i\neq j\in \{1,\ldots ,k\}:v\in V_{i}\wedge w\in V_{j}\rightarrow \{v,w\}\in E} .

Mit K n 1 , … … , n k {\displaystyle K_{n_{1},\ldots ,n_{k}}} notiert man einen vollständig k-partiten Graphen, mit | V i | = n i {\displaystyle |V_{i}|=n_{i}} .

Die Turán-Graphen T m ( n ) {\displaystyle T_{m}(n)} ( 3 ≤ ≤ m < n {\displaystyle 3\leq m<n} ) sind vollständige m {\displaystyle m} -partite Graphen. Das nebenstehende Beispiel T 3 ( 7 ) {\displaystyle T_{3}(7)} ist 3-partit. Bezeichnet ⌊ ⌊ ⋅ ⋅ ⌋ ⌋ {\displaystyle \lfloor \cdot \rfloor } die Floor-Funktion, so ist

T m ( n ) = K ⌊ ⌊ n m ⌋ ⌋ , ⌊ ⌊ n + 1 m ⌋ ⌋ , … … , ⌊ ⌊ n + m − − 1 m ⌋ ⌋ {\displaystyle T_{m}(n)=K_{\lfloor {\frac {n}{m}}\rfloor ,\lfloor {\frac {n+1}{m}}\rfloor ,\ldots ,\lfloor {\frac {n+m-1}{m}}\rfloor }} .

Für das nebenstehende Beispiel gilt damit

T 3 ( 7 ) = K 2 , 2 , 3 {\displaystyle T_{3}(7)=K_{2,2,3}} .

• Jeder k-partite Graph ist k-knotenfärbbar. Dabei wird jeder Partitionsklasse eine Farbe zugewiesen. Die Frage, ob ein Graph k-partit ist, ist also äquivalent zu der Frage, ob der Graph k-knotenfärbbar ist. Die chromatische Zahl eines Graphen G {\displaystyle G} ist somit das kleinste k {\displaystyle k} , sodass G {\displaystyle G} eine k-Partition besitzt.

• Jeder k-partite Graph ist auch immer ein k+x-partiter Graph, wobei x eine natürliche Zahl und k+x kleiner als die Knotenzahl ist.

• Ein vollständig k-partiter Graph K n 1 , … … , n k {\displaystyle K_{n_{1},\ldots ,n_{k}}} mit n 1 ≤ ≤ … … ≤ ≤ n k {\displaystyle n_{1}\leq \ldots \leq n_{k}} besitzt immer ein Matching der Größe min { ∑ ∑ i = 1 k − − 1 n i , ⌊ ⌊ 1 2 ∑ ∑ i = 1 k n i ⌋ ⌋ } {\displaystyle \min\{\sum _{i=1}^{k-1}n_{i},\lfloor {\frac {1}{2}}\sum _{i=1}^{k}n_{i}\rfloor \}} , welches effizient berechnet werden kann.cite-ref-1[1]

• Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (diestel-graph-theory.com).

• Eric W. Weisstein: k-Partite Graph. In: MathWorld (englisch).

• Eric W. Weisstein: Complete k-Partite Graph. In: MathWorld (englisch).

• Boris Bukh, Kevin Ferguson: k-partite graph. In: PlanetMath. (englisch)

cite-note-11. ↑ D. Sitton: Maximum Matchings in complete multipartite Graphs. In: Electronic Journal of Undergraduate Mathematics. Volume 00, 1996, S. 6–16.